//给你一个整数数组 nums 和一个 正 整数 k 。
//
// nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ： 
//
// 
// (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x 
//- 1]) % k 
// 返回 
//nums 的 
//最长
//有效子序列 的长度。
//
// 
//
// 示例 1： 
//
// 
// 输入：nums = [1,2,3,4,5], k = 2 
// 
//
// 输出：5 
//
// 解释： 
//
// 最长有效子序列是 [1, 2, 3, 4, 5] 。 
//
// 示例 2： 
//
// 
// 输入：nums = [1,4,2,3,1,4], k = 3 
// 
//
// 输出：4 
//
// 解释： 
//
// 最长有效子序列是 [1, 4, 1, 4] 。 
//
// 
//
// 提示： 
//
// 
// 2 <= nums.length <= 10³ 
// 1 <= nums[i] <= 10⁷ 
// 1 <= k <= 10³ 
// 
//
// Related Topics 数组 动态规划 👍 37 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-07-17 21:16:22
 * @description 3202.找出有效子序列的最大长度 II
 */
public class FindTheMaximumLengthOfValidSubsequenceIi{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindTheMaximumLengthOfValidSubsequenceIi fun=new FindTheMaximumLengthOfValidSubsequenceIi();
	 	 Solution solution = fun.new Solution();
			solution.maximumLength(new int[]{1, 2, 3}, 3); // 输出：3
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 先考虑连续的情况，构建一个临接和数组，直接判断其中元素相等的最大长度
	//对于非连续的情况
	/*
	* (a + b) % k = (b + c) % k
	(a + b - b - c) % k = 0
	(a - c) % k = 0
	即 a % k == c % k
	(b + c) % k = (c + d) % k ⇒ b % k == d % k
	因此，可以推导出：
	子序列中奇数位的元素模 k 同余，偶数位的元素模 k 同余。
	即：
	sub[0] % k == sub[2] % k == sub[4] % k == ...
	sub[1] % k == sub[3] % k == sub[5] % k == ...
	因此，最长有效子序列可以看作是：
	奇数位和偶数位分别满足模 k 同余的交替序列。

	定义dp[i][j]
	表示以ij作为最后元素的最长有效子序列长度，
	* 初始i<j，dp[i][j]=2
	* 对于每个k<i<j，找到l<k使得nums[l]+nums[k] % k == nums[k]+nums[i] % k
	* 等价于nums[l]% k == nums[i] % k
	* 更新dp[k][i]=dp[l][k]+1，nums[l] % k == nums[i] % k
	* 在所有满足l<k且nums[l] % k == nums[i] % k的l中，取最大值
	* */
		 public int maximumLength1(int[] nums, int k) {
			 int[][] dp = new int[k][k];
			 int res = 0;
			 for (int num : nums) {
				 num %= k;
				 for (int prev = 0; prev < k; prev++) {
					 // 如果当前数和前一个数模k相等，则可以构成有效子序列
					 //找出所有满足nums[l] % k == nums[i] % k的l
					 // 如果dp[prev][num] == 0，说明没有有效子序列

					 //说白了，奇数和偶数位的元素模 k 同余
					 //最终的子序列每个位上只有两种可能性
					 //先确定num%k，再确定prev
					 dp[prev][num] = dp[num][prev] + 1;
					 // 更新最大长度
					 // 01 11 21 +1
					 // 02 12 22 +1
					 // 01 11 21 +1
					 res = Math.max(res, dp[prev][num]);
				 }
			 }
			 return res;
		 }
		 /*
		 * 时间复杂度：O(k(k+n))，其中 n 是 nums 的长度。注意创建大小为 k 的数组需要 O(k) 的时间。
			空间复杂度：O(k)。
		 * */
	public int maximumLength(int[] nums, int k) {
		int ans = 0;
		for (int m = 0; m < k; m++) {
			int[] f = new int[k];
			for (int x : nums) {
				// 计算当前数模 k 的值
				x %= k;
				//如果已经知道了子序列最后一项，那么倒数第二项可以通过k推断出来
				//对于x=nums[i],我们可以在最后一项为
				//(m-xmodk+k)mod k的子序列添加x，那么
				//fx = f[(m - x + k) % k] + 1;
				f[x] = f[(m - x + k) % k] + 1;
				ans = Math.max(ans, f[x]);
			}
		}
		return ans;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
